import random
import copy
import sys # for exit
title = "The meaning of life"

# utils functions
# -----------------------------------------------------------------------

# pack all with no checks 
# def pack_all(pool):
#     knapsack = []
#     for i in pool:
#         knapsack.insert(i['id'], 1)        
#     return knapsack

# put one lightest item if it is possible in case nothing placed
def patch_stupid (pool, capacity):
    minweight = pool[0]['weight']
    minindex = 0
    
    for i in range(0, len(pool)):
        if pool[i]['weight'] < minindex:
            minindex = i
            minweight = pool[i]['weight']
    
    knapsack = []
    for i in range(0,len(pool)):
        knapsack.append(0)
    if minweight <= capacity:
        knapsack[i] = 1
    return knapsack     
    
# generate one possible random solution    
def stupid_pack(pool, capacity):
    knapsack = []
    for i in range(0,len(pool)):
        knapsack.append(0)
    load = 0.0
    
    full = False
    count = 0
    while full == False:
        i = random.randrange(0, len(pool))
        if not knapsack[i]: # if item is NOT packed
            if load + pool[i]['weight'] > capacity:
                # cannot pack item, assume knapsack is full already
                full = True
            else:
                # pack it
                knapsack[i] = 1
                count += 1
                load += pool[i]['weight']                 
                if count == len(knapsack):
                    full = True
    if load == 0:
        knapsack = patch_stupid (pool, capacity)  
    return knapsack
    
# get one random solution with no possibility checks    
def randgene(pool):
    knapsack = []
    for i in pool:
        knapsack.append(random.choice([0,1]))
    return knapsack

# get a population of guaranteed possible gens-solutions for genetic algorithm
def possible_pop(pool, capacity, size):
    p = [] # population
    for i in range(0, size):
        p.append(stupid_pack(pool, capacity))
    return p
     
# get absolutely random population for genetic algorithm    
def rand_pop(pool, capacity, size):
    p = [] # population
    for i in range(0, size):
        p.append(randgene(pool))
    return p

def sortby(somelist, n):
    nlist = [(x[n], x) for x in somelist]
    nlist.sort()
    return [val for (key, val) in nlist]
    
# print population in gene value manner           
def showpop(p, pool, capacity):
    for gene in p:
        showgene(gene, pool, capacity)        
def showgene(gene, pool, capacity):
    print (gene, " p:",  priceup(gene, pool), " w:", weighup(gene, pool), " h:", hevaluate (gene, pool, capacity))
    
# maked a list of items from gene
def genetolist(gene, pool):
    items = []
    for i in range(0, len(gene)):
        if gene[i]: # if is put
            items.append(pool[i])
    return items              

# END of utils functions
# -----------------------------------------------------------------------

# weigh up the knapsack
def weighup (gene, pool):
    weight = 0.0
    for i in range(0, len(gene)):
        if gene[i]:
            weight = weight + pool[i]['weight']
    return weight

# get total price of items in the knapsack
def priceup (gene, pool):
    price = 0.0
    for i in range(0, len(gene)):
        if gene[i]:
            price = price + pool[i]['price']
    return price

# get heuristic evaluation of a gene    
def hevaluate (gene, pool, capacity):
    weight = 0.0
    price = 0.0
    
    for i in range(0, len(gene)):
        if gene[i]:
            weight = weight + pool[i]['weight']
            price = price + pool[i]['price']
    
    heuristics = price
    if weight <= capacity:
        heuristics = heuristics**2
        
    return heuristics

# get the best gene from the population
def getbestgene(p, pool, capacity):
    best = {"heurisics":0,"price":0,"weight":0,"gene":[]}    
    for i in range(0, len(p)):
        gene = p[i]
        weight = weighup(gene, pool)
        if weight > capacity: # if does not fit, we are not interested
            break
        price = priceup(gene, pool)
        if price > best['price']:
            best['heuristics'] = hevaluate(gene, pool, capacity)
            best['price'] = price
            best['weight'] = weight
            best['gene'] = gene
    return best['gene']      

# genetic packing algorithm
# pool - pool of items, capacity - maximal knapcack payload    
def genetic(pool, capacity):
    # default settings 
    popsize = 4 # size of initial population, conditionally const value
    itercount = 100 # count of iterations
    
    # generate initial population
    if len(pool) < 10:
        children = possible_pop(pool, capacity, popsize) 
        itercount = 250
    else:        
        children = possible_pop(pool, capacity, popsize)
        itercount = 100
    
    for generation_change in range(0, itercount):
        parents = children
        children = list()
        
        # prepare parents for crossing
        tmp = []    
        for gene in parents:
            value = hevaluate(gene, pool, capacity)
            tmp.append((gene, value))
        tmp = sortby(tmp, 1)
        parents = []    
        for t in tmp:
            parents.append(t[0])
        parents.reverse()
        
        # clone the two best ones
        parents.append(parents[0])
        parents.append(parents[1])
        
        # cross
        cut = random.randrange(1,len(pool)-1) # gen cutting point
        
        while len(parents) >= 2:    
            i = random.randrange(0, len(parents))
            p1 = parents[i]
            del parents[i]
            
            i = random.randrange(0, len(parents))
            p2 = parents[i]
            del parents[i]
            
            c1 = p1[0:cut] + p2[cut:] 
            c2 = p2[0:cut] + p1[cut:]
            
            children.append(c1)        
            children.append(c2)
    
    knapsack = getbestgene(children, pool, capacity)
    knapsack = genetolist(knapsack, pool) 
    return knapsack
    
# get the best gene from the array using heuristics
def bestitem (values, genes):
    maxvalue = 0.0
    maxitem = []
    for v, g in zip (values, genes):
        if v > maxvalue:
            maxvalue = v
            maxitem = g
    return maxitem       
        
def walk(vertex, pool, capacity):
    if len(vertex) == len(pool):
        return vertex
    else:
        vertex0 = vertex + [0] # possible descendants
        vertex1 = vertex + [1] # 
        
        left = walk(vertex0, pool, capacity)
        if weighup(vertex1, pool) > capacity: # if the solution is possible
            return left
        else:
            right = walk(vertex1, pool, capacity)
            if priceup(left, pool) >= priceup(right, pool):
                return left
            return right
            
# branch and bound        
def bb(pool, capacity):
    root = []
    knapsack = walk(root, pool, capacity)
    knapsack = genetolist(knapsack, pool)
    return knapsack
             
# WRONG tree-walk for brench and bound             
def wrong_walk(vertex, pool, capacity):
    next = [] # descendants - possible solutions
    values = [] # total prices of descendants 
    
    for i in range(0, len(vertex)):
        if vertex[i] == 0:
            temp = copy.copy(vertex)
            temp[i] = 1
            weight = weighup(temp, pool)
            if weight <= capacity: 
                next.append(temp)
    
    if len(next) > 0:
        for i in range(0, len(next)):
            next.insert(i, wrong_walk(next[i], pool, capacity))
            values.insert(i, priceup(next[i], pool))
        return bestitem(values, next)
    else:
        return vertex
             
# wrong approach to branch and bound        
def wrongbb(pool, capacity):
    root = []
    for i in range(0, len(pool)):
        root.append(0)
    knapsack = wrong_walk(root, pool, capacity)
    knapsack = genetolist(knapsack, pool)
    return knapsack
    

